This invention relates to a FIFO (First-In First-Out) memory circuit, and more particularly, to a synchronized FIFO memory circuit.
The term FIFO is an acronym for a First-In/First-Out memory, meaning a memory outputting data which was inputted first.
The FIFO is a functional storage device that is interposed between two apparatuses wherein data produced in a time series from one of the apparatuses is inputted to the other apparatus. The FIFO is placed between the two apparatuses as a memory buffer for absorbing a difference in processing speed and/or processing timing between the two apparatus.
Generally, FIFO memories are roughly divided into two types depending upon the configuration of a storage element of the FIFO.
One of the FIFO memories employs a random access memory as a storage element. In order to allow a random access memory to operate as a FIFO, it is combined with a FIFO controller to construct a FIFO. As a random access memory, an SRAM or a register file is used. The FIFO controller is a sequential circuit that includes a write pointer, i.e. a register indicating a write position for input data and a read pointer, i.e. a register indicating a read position for output data.
The other one of the FIFO memories employs a shift register including a plurality of registers connected at the same plurality of stages. The registers have a sequential relationship among them and transfer all pieces of data at a time from each register nearer to the input to an adjacent register nearer to the output.
Further, the FIFO memories are roughly divided into two types from a functional point of view.
One of the FIFO memories is generally called an asynchronous FIFO with the write timing and the read timing thereof different from each other. Writing is performed in synchronism with a signal called a write clock, and reading is performed in synchronism with a signal called a read clock.
The other one of the FIFO memories is generally called a synchronized FIFO with the write timing and the read timing thereof matching each other. Writing and reading are performed in response to a common input clock. A write enable signal and a read enable signal determine whether writing should be or should not be performed and whether reading should be or should not be performed respectively.
1) FIFO with no Input/Output Registers
A block diagram of a conventional synchronized FIFO of the random access memory type and a FIFO controller thereof is shown in FIG. 1.
Referring to FIG. 1, a block denoted by 1R1W MEMORY is a typical 1-read/1-write random access memory having no input register and no output register. The 1-read/1-write random access memory has data input/output terminals, a write address input terminal/read address input terminal and a write enable (Write Enable) signal input terminal/read enable (Read Enable) signal input terminal.
The FIFO controller controls write/read addresses and write/read enable signals to cause the random access memory to operate as a FIFO. For this reason, the FIFO controller includes a Write Pointer Counter for holding and updating a write address and a Read Pointer Counter for holding and updating a read address.
Generally, two kinds of operation, namely, writing and reading, are performed on the FIFO. For this reason, the FIFO controller has a Write Enable signal input for requesting writing and a Read Enable signal input for requesting reading. Further, the FIFO controller has signals indicating status of the FIFO. The status signals are a Full signal output indicating whether or not a write operation is enabled (a write operation is disabled when Full==0) and an Empty signal output indicating whether or not a read operation is enabled (a read operation is disabled when Empty==1). Or, since a write operation is enabled when Full==0 and a read operation is enabled when Empty==0, the FIFO controller may output a signal of Write Ready (=xcx9cFull) or Read Ready (=xcx9cEmpty). The signals are all managed by the FIFO controller.
The Write Pointer (hereinafter referred to as a WP) indicates a position into which input data is to be written, and the Read Pointer (hereinafter referred to as an RP) indicates a position from which data is to be read out. If the WP and the RP indicate the same position, this represents that no valid entry (a register in which data is stored) is present. In this instance, the Empty signal is 1.
The number of valid entries is the number of pieces of valid data present in the FIFO and is given by (WPxe2x88x92RP). This, however, is limited to a case wherein the maximum number of entries in the FIFO is 2{circumflex over ( )}n (where n is a natural number).
The number of entries that can be stored in the FIFO may be equal to the maximum number of entries, or may be equal to the maximum number of entries xe2x88x921, depending upon the manner of control of the FIFO. When as many pieces of data as all entries are simply written into the FIFO at a point of time, then a WP=RP state is reached at the point of time, and this full state cannot be distinguished from the condition of an empty FIFO. Accordingly, a 1-bit register needs to be provided separately to allow discrimination between the Empty and Full states of the FIFO depending upon whether or not WP=RP.
Another method is available wherein WP=RPxe2x88x921 is regarded as a condition of a full FIFO. In this instance,
WP=RP+nxe2x88x921(mod n)=RPxe2x88x921(mod n)
where the symbol n represents the maximum number of entries, and the number of entries that can be stored in the FIFO is given by the maximum number of entries xe2x88x921. Here, RP+1xe2x88x92n(mod n) signifies a remainder that is obtained when RP+nxe2x88x921 is divided by n. Similarly, RP-1(mod n) is a remainder that is obtained when RP-1 is divided by n. The transformation of the expression above is obvious. In FIG. 1, an example wherein the number of entries that can be stored in the FIFO is equal to maximum number of entries xe2x88x921 is shown.
Further, depending upon the application of the FIFO, the FIFO controller may have Almost Full and Almost Empty signals.
The Almost Full and Almost Empty signals have the value 1 when the number of remaining empty entries is smaller than a number of entries i and the number of valid entries is smaller than a number of entries j, respectively. In order to implement the FIFO controller with this feature, suitable constants should be inputted to comparators as seen from FIG. 1.
2) FIFO with Input/Out Registers
The FIFO memory having no input register and no output register provided therefor has been described above. However, if the capacity of the memory becomes so large that a considerable time is required to write and read out data into and from the memory, then a state in which input data has to be delivered at the beginning of a cycle and read data is received at the end of the cycle becomes inevitable. Generally, in such a case, a data input register, i.e. Input Register, and a data output register, i.e. Output Register, are provided for the data input and output terminals of the memory respectively as seen in FIG. 2.
Where no such input/output registers are provided, the relationships of Write Ready=xcx9cFull and Read Readyxe2x88x92xcx9cEmpty are satisfied. On the other hand, if the input register has valid data therein and the memory is Full while the output register is empty, the FIFO as a whole is not Full since the output register is one of entries of the FIFO. Nevertheless, the FIFO is not Read Ready. This is because the valid data in the input register cannot be transferred to the memory. Further, although the memory is not Empty, it is not Read Ready. This is because the output register has no valid data. In this instance, it is possible merely to read out data in the memory designated by the RP and transfer it to the output register. Thereafter, since one empty entry appears, the data in the input register is transferred to the memory and input data is written into the input register simultaneously. It can be noted that an ordinary memory does not allow simultaneous reading and writing from and into the same address. On the other hand, an ordinary register allows simultaneous reading and writing.
Accordingly, for a FIFO that includes an input register and an output register, logic for generating Write Ready and Read Ready signals must be prepared separately. (In FIG. 2, the logic is included in the FIFO controller.)
Further, in order to generate Almost Full and Almost Empty signals, it is necessary to acquire the number of valid entries in the FIFO. However, with the FIFO having input/output registers, the number of valid entries cannot be obtained correctly by mere subtraction of RP from WP (WP-RP). The number of pieces of valid data in the input/output registers must also be taken into account.
In particular, let logical values of the propositions xe2x80x98The input register has valid dataxe2x80x99 and xe2x80x98The output register has valid dataxe2x80x99 be represented by IR and OR, respectively. In this case, the total number of valid entries in the FIFO must be determined in accordance with the following:
Total number of valid entries in FIFO=(the number of valid entries in memory+IR+OR)
This can be achieved, as seen from FIG. 2, by adding two adders to the FIFO controller shown in FIG. 1.
It is to be noted that the output terminals for signals indicating the Full and Empty states of the FIFO controller shown in FIG. 1 are not provided in the FIFO controller shown in FIG. 2.
However, generation of Write Ready and Read Ready described above relates to Full and Empty states of entries in the memory, and they must be generated by a similar means to that of the FIFO controller of FIG. 1. Comparators for generation of the signals are shown also in FIG. 2.
As described above, the status signals (Full, Empty, Almost Full and Almost Empty) of the FIFO are produced by subtraction (addition) and comparison. The control logic (Controller in FIG. 2) in the FIFO controller produces control signals for production of a next status based on the current status and inputs (Write Enable and Read Enable) thereto. Updating of the WP and the RP is controlled by signals produced at this time.
Accordingly, a path that begins with operations to refer to the WP and the RP and ends with operations to update the WP and the RP is present as shown in FIG. 3, and this becomes a critical path, i.e. a maximum delay path, in the FIFO controller.
Meanwhile, a FIFO status signal is also referred to by an external apparatus connected to the FIFO. A status signal of the FIFO may relate to updating of a register in a logic circuit of an external apparatus as seen from FIG. 4 or FIG. 5, and this may probably make a critical path. It is to be noted that FIG. 4 shows a FIFO controller for a FIFO with no input/output registers while FIG. 5 shows a FIFO controller for a FIFO with input/output registers.
A feature common to the arrangements shown in FIGS. 3, 4 and 5 is a path up to production of a FIFO status signal. The conventional FIFO controllers have a problem in that, since a plurality of steps including subtraction (addition) and comparison are involved, a long delay time is entailed.
Particularly where a critical path of the entire apparatus is a path for referring to a FIFO of an apparatus outside the FIFO, a status signal of the FIFO must be generated as fast as possible, and it is desirable that a status signal of the FIFO be updated at the beginning of a clock cycle.
It is thus an object of the present invention to provide a synchronized FIFO memory circuit of the random access memory type wherein a circuit configuration of a FIFO controller is improved by reducing the length of a critical path in the FIFO controller to raise the operating speed of the FIFO controller itself, thereby to increase the operating speed of the entire FIFO memory.
In order to attain the object described above, according to an aspect of the present invention, there is provided a synchronized FIFO memory circuit that includes a random access memory and a FIFO controller, comprising a first counter for counting a number representing a Read Pointer, a second counter for counting a number representing a Write Pointer, a third counter for holding and managing the number of remaining empty entries of the FIFO memory circuit, and comparison means for comparing a value of the third counter with a constant value to produce status signals of the FIFO memory circuit, namely, Write Ready, Read Ready, Full, Empty, Almost Full and Almost Empty at a high speed.
According to another aspect of the present invention, there is provided a synchronized FIFO memory circuit that includes a random access memory and a FIFO controller, comprising a first counter for counting a number representing a Read Pointer, a second counter for counting a number representing a Write Pointer, a third counter for holding and managing the number of valid entries in the FIFO memory circuit, and comparison means for comparing a value of the third counter with a constant value to produce status signals of the FIFO memory circuit, namely, Write Ready, Read Ready, Full, Empty, Almost Full and Almost Empty at a high speed.
Each of the synchronized FIFO memory circuits described above may comprise, in place of the comparison means, one or a plurality of status look-ahead means for comparing the value of the third counter with the constant value to determine the status signals of the FIFO memory circuit, namely, Write Ready, Read Ready, Full, Empty, Almost Full and Almost Empty for a t-th cycle within a (txe2x88x921)-th cycle and to output the status signals at the beginning of the t-th cycle.